//给你一个整数 n 和一个二维整数数组 queries。 
//
// 有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。 
//
// queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最
//短路径的长度。 
//
// 返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，
//从城市 0 到城市 n - 1 的最短路径的长度。 
//
// 
//
// 示例 1： 
//
// 
// 输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]] 
// 
//
// 输出： [3, 2, 1] 
//
// 解释： 
//
// 
//
// 新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。 
//
// 
//
// 新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。 
//
// 
//
// 新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。 
//
// 示例 2： 
//
// 
// 输入： n = 4, queries = [[0, 3], [0, 2]] 
// 
//
// 输出： [1, 1] 
//
// 解释： 
//
// 
//
// 新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。 
//
// 
//
// 新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。 
//
// 
//
// 提示： 
//
// 
// 3 <= n <= 500 
// 1 <= queries.length <= 500 
// queries[i].length == 2 
// 0 <= queries[i][0] < queries[i][1] < n 
// 1 < queries[i][1] - queries[i][0] 
// 查询中没有重复的道路。 
// 
//
// Related Topics 广度优先搜索 图 数组 👍 67 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//java:新增道路查询后的最短距离 I
public class Q3243ShortestDistanceAfterRoadAdditionQueriesI {
    public static void main(String[] args){
        Solution solution = new Q3243ShortestDistanceAfterRoadAdditionQueriesI().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
            List<Integer>[] g = new ArrayList[n - 1];
            Arrays.setAll(g, i -> new ArrayList<>());
            for (int i = 0; i < n - 1; i++) {
                g[i].add(i + 1);
            }

            int[] ans = new int[queries.length];
            int[] vis = new int[n - 1];
            for (int i = 0; i < queries.length; i++) {
                g[queries[i][0]].add(queries[i][1]);
                ans[i] = bfs(i + 1, g, vis, n);
            }
            return ans;
        }

        private int bfs(int i, List<Integer>[] g, int[] vis, int n) {
            List<Integer> q = new ArrayList<>();
            q.add(0);
            for (int step = 1; ; step++) {
                List<Integer> tmp = q;
                q = new ArrayList<>();
                for (int x : tmp) {
                    for (int y : g[x]) {
                        if (y == n - 1) {
                            return step;
                        }
                        if (vis[y] != i) {
                            vis[y] = i;
                            q.add(y);
                        }
                    }
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}